DATA STRUCTURES INDEX

Arborele oarecare are:
- un nod radacina care are descendenti dar nu are nod parinte
- numarul de descendenti variaza de la un nod intermediar la alt nod intermediar
- numarul de noduri frunza difera de la un nod de pe penultimul nivel, la un alt nod de pe penultimul nivel.
Arborele oarecare se reprezinta prin:
- nod cu vector de pointeri cu numar oarecare de elemente, depinzand de numarul de descendenti
- vector de pointeri cu numar fix de componente, numarul de componente fiind egal cu numarul maxim de descendenti.
back

ARBORE AVL

Este arborele echilibrat dupa inaltime.
Adelson, Velskii si Landis au definit structura de date in care intre inaltimile subarborilor unui arbore binar diferenta este cel mult unu.
Starea inaltimii subarborilor se modifica la adaugarea de noduri.
Daca se presupune ca un nod se adauga subarborelui stang, se identifica urmatoarele situatii:
- daca inainte de adaugare inaltimile subarborilor sunt identice, arborele ramane AVL
- daca inaltimea subarborelui drept este mai mare decat inaltimea subarborelui stang este mai mare, dupa adaugare, creste inaltimea subarborelui stang, cele doua inatimi devenind egale, arborele ramanand AVL
- daca inaltimea subarborelui stang este mai mare decat cea a subarborelui drept, prin adaugarea nodului la subarborele stang, diferenta dintre cele doua inaltimi este mai mare ca unu.
Arborele nu mai este AVL si trebuie sa fie reechilibrat.
back

ARBORE MULTICAI

Este o structura arborescenta in care nodurile contin pointeri catre un numar fix de descendenti.
Cazul in care numarul de descendenti este 2 este caz particular.
Acesti arbori sunt utilizati cand este vorba de numar mare de articole.
Daca numarul de pointeri pentru descendenti este M, numarul de niveluri ale arborelui multicai este mai redus.
Pentru localizarea articolelor in fisier variabilele pointer sunt inlocuite cu variabile ce contin pozitia articolelor in fisier.
back

(a-b) ARBORI

Acesti arbori sunt cu noduri definite pentru a realiza legatura cu un numar de descendenti x, care indeplineste conditiile urmatoare:
- numarul maxim de descendenti este b
- numarul minim de descendenti este a
- frunzele arborelui se afla pe acelasi nivel
- numerele a si b indeplinesc conditiile 2<=a si 2a-1<=b
Cheile dupa care se face stocarea articolelor sunt dispuse in ordine crescatoare.
Arborele (a-b)este de cautare bazat pe aceasta restrictie asupra ordonarii cheilor.
back

ALOCARE / DEALOCARE MEMORIE

Alocarea de memorie in timpul executiei unui program se executa cu procedura malloc()
Dealocarea de zone de memorie se realizeaza in timpul executiei unui program cu procedura free().
Limbajul C++ permite alocarea de memorie cu functia new(), iar dealocarea cu delete().
back

AUDITARE STRUCTURI DE DATE

Proces prin care se stabileste masura in care este realizata concordanta intre specificatiile de programare si programul deja construit in ceea ce priveste structurile de date alese.
Se verifica daca:
- atructura de date aleasa este buna in raport cu obiectivul urmarit
- se pot implementa cu usurinta operatiile pe structura aleasa
- gradul de ocupare este bun
- exista cazuri in care utilizatorul nu-0si poate rezolva o problema pentru ca structura de date nu are resurse suficiente
- exdpresiile de referire sunt greoaie
- noi functii de prelucrare ce se impun a fi dezvoltate sunt implementate dificil.
Auditul este o activitate in care este analizat cat de bine a fost aleasa structura de date.
daca de exemplu, pentru a elabora un program de calcul medie aritmetica este ales vectorul, aceasta structura de date este neadecvata daca:
- dimensiunea seriei de date are variatii foarte mari
- problema de prelucrare trebuie reluata
- apar situatii in care numarul de termeni ai seriei este mai mare decat memoria alocata pentru vector.
Vectorul este inlocuit cu:
- un fisier in care se stocheaza seria de termeni pentru a putea fi reluata problema
- o lista in care informatia utila este preluata din fisier.
Auditorul trebuie sa:
- constate neconcordantele
- identifice solutiile slabe
- demonstreze ca alta structura vine cu avantaje.
Auditul structurilor de date are in atentie:
- domeniul de variatie a structurii
- comportamentul structurii
- riscurile de eroare datorate initializarilor incorecte pentru variabile pointer
- controlul mentinerii la referirea elementelor din structura si nu in afara ei.
- semnalarea prin mesaje proprii programului a situatiilor de exceptie in prelucrare.
back

B-arbore

Structura de date dinamica in care prin modul in care este construita este asigurat caracterul echilibrat.
Se considera o colectivitate formata din elementele E1, E2, E3,...,En.
Elementele sunt ordonate crescator functie de valoarea unui camp unic numit cheie.
Un nod are informatia utila corespunzatoare mai multor elemente dintr-o colectivitate.
Daca un nod memoreaza informatiile despre P elemente din colectivitate, numarul de noduri care formeaza arborele B depinde de valoarea lui n (numar de elemente din colectivitate) si de P (ordinul arborelui B).
Se mentine ordinea crescatoare a articolelor.
Se aloca memorie pentru un nou nod daca si numai daca au fost ocupate cele P elemente ale nodului curent.
Exista biblioteci de programe care:
- creaza noduri pentru arbori B
- insereaza articole in nod
- leaga nodul ca descendent stang sau drept
- asigura ca diferenta dintre inaltimile subarborilor sa nu depaseasca unitatea.
back

CAP LISTA SIMPLA

Primul element al listei simple.
Adresa acestui element este memorata in variabila pointer cu care se refera lista simpla.
Uneori se confunda conceptul de cap de lista cu insusi variabila pointer.
Aceasta confuzie trebuie eliminata.
back

CAP LISTA DUBLA

Primul element al listei duble.
Adresa acestui element este memorata in variabila pointer cu care se refera lista dubla care se poarcurge utilizand pointerul care refera urmatorul element din lista.
Ultimul element din lista, element a carui adresa se memoreaza intr-o variabila pointer atunci cand referirea se face spre elementul precedent.
Traversarea se efectueaza de la ultimul spre primul element.
Uneori se confunda conceptul de cap de lista cu insusi variabila pointer.
Aceasta confuzie trebuie eliminata.
back

CAP STIVA / VARF STIVA

Ultimul element introdus in stiva cu functia PUSH.
Adresa acestui element este memorata in variabila pointer numita pointer spre varful stivei, variabila cu care se refera elementele stivei pe masura ce se face alocare sau dealocare.
Uneori se confunda conceptul de varf al stivei, care este ultimul element legat prin PUSH de structura stiva cu insusi variabila pointer care refera acest element.
Aceasta confuzie trebuie eliminata.
back

CHEIE UNICA

In structura de tip articol se defineste un camp numit CHEIE.
Acest camp este astfel ales incat pentru fiecare element al unei colectivitati este asigurata unicitatea.
Codul numeric personal este campul care poate fi cheie de identificare a cetatenilor, intrucat are caracter unic.
Fiecare combinatie de 13 cifre este asociata unei singure persoane din tara.
Codul materialului este cheie.
La proiectarea fisierului de materiale se are in vedere ca acest cod sa fie unic.
Codul uni material NU se mai atribuie si altor materiale.
Marca muncitorului, numarul matricol al strudentului, sunt de asemenea chei unice.
Codurile judetelor si ale Municipiului Bucuresti aunt chei unice utilizate la construirea numarului pentru autovehicule.
NU trebuie sa fie doua autovehicule diferite cu acelasi numar de inmatriculare.
Cheile unice sunt utilizate pentru a pune ordine in fisiere si in baze de date.
Dispunerea in tabele se face dupa sortarea datelor in raport cu cxheile unice.
Sortarea se face in ordine crescaqtoare sau descrescatoare.
back

ARBORE BINAR

Contine:
- definire clasa
- definire structura autoreferita pentru noduri(pointeri, informatie utila
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor definite pentru lucru cu arbori binari.
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu arbori binari.
back

CICLUL DE DEZVOLTARE

Este reprezentat de urmatoarele etape necesare realizarii unui program:
- definirea problemei din care rezulta: ca de omogene sunt datele, cum se regrupeaza, care este volumul lor
- stabilirea algoritmilor din care se vede: repetitivitatea introducerii datelor, ce date trebuie sa se afle in memorie pentru a calcula expresii, ce actualizari se fac
- elaborarea de diagrame, specificatii cu date de test
- alegerea structurilor de date statice, dinamice cu justificari clare
- elaborare de cod orientat pe structurile de date folosite
- testarea pe exemplele din specificatii
- implementarea
- mentenanta
- reingineria cu schimbari calitative in primul rand la nivelul structurilor de date.
Daca se doreste realizarea unui program pentru calculul de medii cu numar mare dar necunoscut de termeni:
- se alege lucrul cu liste simple
- datele se vor stoca in fisier si de acolo se aduc in lista
- programul calculeaza prin traversarea listei, suma elementelor seriei
- programul calculeaza media pe care o afisaza.
Daca este vorba de medie aritmetica ponderata exista doua variante:
- in care un element al listei are informatia utila formata din x[i] si frecventa f[i]
- se construiesc doua liste, una pentru sir si alta pentru frecvente.
Prin compararea celor doua solutii referitor la citiri de doua fisiere, expresii diferite de referire, rezulta ca utilizarea a doua liste nu este eficienta.
back

CLASA ARBORE B

Contine:
- definire clasa
- definire structura autoreferita pentru noduri(pointeri, informatie utila ca vectori de chei si pointeri)
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor definite pentru lucru cu arbori B.
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu arbori B.
back

CLASA LISTA

Contine:
- definire clasa
- definire structura autoreferita pentru noduri(pointerispre elementul urmator, informatie utila )
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor de stergere element, inserare element, cautare dupa cheie, interschimb de elemente, sortare, concatenare, operatii definite pentru lucru cu lista simpla.
In cazul listei duble mai apare pointer spre elementul precedent.
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu liste simple sau cu liste duble.
back

CLASA MATRICE

Contine:
- definire clasa
- definire pointer sapre pinter
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor de initializare din fisier, de calcul norme, supraincarcare operatori pentru adunare, scadere, inmultire, inversare matrice .
In cazul matricelor trebuie gestionate liniile si coloanele incat metodele sa utilizeze numai elemente pentru care au fost alocate zone de memorie si care au fost initializate.
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu matrice.
back

CLASA STIVA

Contine:
- definire clasa
- definire structura autoreferita pentru noduri(pointeri spre elementul urmator, informatie utila )
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor PUSH si POP .
In cazul stivei trebuie implementata regula LIFO .
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu mai multe stive.
Trebuie ca operatiilor de alocare dinamica sa le corespunda si dealocari astfel incat sa nu se satureze stiva definita prin sistemul de operare.
back

CLASA VECTOR

Contine:
- definire clasa
- definire pointer in care se memoreaza adresa unde se aloca elementele vectorului
- definire pointeri
- definire constructor
- definire destructor
- definire metode corespunzatoare operatiilor de initializare din fisier, de calcul norme, supraincarcare operatori pentru adunare, scadere, inmultire, produs scalar, alegere minim, alegere maxim din vector .
In cazul vectorilor trebuie gestionate elemente pentru care au fost alocate zone de memorie si care au fost initializate.
Trebuie avut in vedere sa se asigure:
- completitudinea operatiilor sa nu fie nevoie de a defini multe niveluri de clase derivate
- robustetea fara sa apara intreruperi accidentale in referirea metodelor.
Clasa este construitra astfel incat in programul principal sa fie referite metodele fara a transmite parametri care ar micsora robustetea aplicatiilor cu vectori.
back

GENERALITATE

Este caracteristica pe care trebuie sa o aiba biblioteca de functii construite pentru lucru cu structuri de date.
Programatorul trebuie sa dezvolte astfel de proceduri incat prin apelare, cu cat mai putine modificari sa rezolve problemele pe care le are.
Probleme dificile apar mai ales in ceea ce priveste informatiile utile.
De aceea este important sa fie definite clase in care aceste tipuri sa poata fi adaptate de la o problema la alta folosind template-uri.
back

INSERARE ELEMENT

Daca se considera un element cu cheie KEYY data si se pune problema dispunerii lui intr-o lista astfel incat cheile elementelor sa ramana in ordine crescatoare, operatia de legare a noului element cu elemente deja existente se numeste inserare.
Daca un vector are 17 elemente x[0], x[1], x[2],...,x[16], a insera un element alfa intre elementele x[9] si x[10] inseamna:
- a creste numarul elementelor vectorului la 18
- a deplasa elementele x[16] in x[17], x[15] in x[16] si tot asa pana la deplasarea lui x[10]in x[11]
- a copia pe alfa in x[10].
Daca o lista are informatia utila sortata crescator dupa cheile 1, 7, 40, 43, 77, 105, 221, 222, 278 si daca se impune includerea unui element cu cheia 169 se procedeaza astfel:
- se traverseaza lista si se compara cheia 169 cu cheile elementelor
- procesul de traversare se intrerupe daca cheia precedenta < 169 < cheia urmatoare
- se insereaza elemntul cu cheia 169
- lista va avea elementele cu cheile:
1, 7, 40, 43, 77, 105,169, 221, 222, 278
Inserarea in structuri dinamice revine la a crea noi legaturi intre elementele existente si elementul care este inserat.
back

COADA

Este o structura de date dinamica in care:
- adaugarea de elemente se efectueaza la sfarsitul structurii
- stergerea se efectueaza incepand cu primul element.
Daca se construieste o lista simplu inlantuita si se inzesatreaza cu disciplina FIFO - first in first out, se obtine structura numita COADA.
In romanescul ASEZARE LA COADA inseamna ca o persoana cand vine se aseaza la coada.
Servirea se face in ordinea asezarii la coada.
Cu cat o persoana vine mai tarziu, ocupa un loc mai la coada si va astepta ca toti in fata sa sa fie serviti.
Se observa ca structura numita coada este o structura gen lista care are reguli precise de alocare si mai ales de dealocare de memorie.
Adaugarea se face ca la lista, ultimul element devine dupa adaugare penultim element.
Eliberarea se face ca la stiva.
Elementul din capul listei este eliberat.
Al doilea element devine cap de lista.
Daca se considera coada formata din elementele:
a b f w p 4 7
si se adauga elementele x z q
structura rezultata este:
a b f w p 4 7 x z q
Daca se vor sterge 4 elemente, acestea vor fi primele patru si dupa eliberarea zonelor de memorie, structura coada va contine:
p 4 7 zx z q
back

CONCATENARE STRUCTURI

Procedeu de alipire a unei structuri de date la o alta structura de date de acelasi tip.
Daca se concateneaza o lista simpla cu N elemente la o lista simpla cu M elemente, va rezulta o lista simpla cu M+N elemente.
Concatenarea este operatie necomutativa.
Concatenand doi arbori binari, va rezulta un arbore binar in care cei doi arbori devin subarbori ai arborelui rezultat.
back

CONSTRUIRE STRUCTURI

Construirea unui element presupune:
- alocare de memorie
- initializarea cu NULL a variabilelor pointer de legatura
- initializarea cu validare a informatiei utile din structura.
Construirea unei structuri de date presupune:
- un proces iterativ
- preluarea unuyi element alocat si initializat
- legarea elementului preluat de celelalte elemente dinstructura prin utilizarea adreselor de zone de memorie.
back

COPIERE STRUCTURI

Presupune:
- construirea unei noi structuri de date de acelasi tip cu structura care face obiectul copierii
- traversarea unei structuri de date
- alocarea de zona de memorie pentru un element dintr-o noua structura de date
- copierea informatiei utile din structura de date traversata
- adaugarea elementului initializat la noua structura de date.
Copierea unei liste simple conduce la a obtine o noua lista simpla in care informatia utila este identica cu informatia din lista supusa copierii.
Variavilele pointer de legatura au valori ce permit referirea de zone de memorie total diferite ca pozitie fizica, ale celor doua liste simple.
back

CAUTARE ELEMENT

Daca se considera o structura de date ale caror elemente sunt identificate printr-un camp numit CHEIE, procesul de cautare presupune:
- traversarea structurii
- copararea cheii elementului referit cu cheia ce trebuie gasita
- returnarea adresei elementului care are cheia dupa care s-a facut cautarea
- returnarea NULL daca nu a fost gasit nici un element cu cheia pentru care a fost declansat procesul de cautare.
back

CONVERSIE STRUCTURI

Conversia structurilor de date este procesul prin care pornind de la o structura de date Si se construieste o alta structura de date Sj, folosind numai informatia utila a structurii Si.
Cu elementele unui vector ca informatie utila se construieste un arbore binar.
cu articolele dintr-un fisier se initializeaza un vector de structura.
Cu informatia utila dintr-o lista simpla se construieste un fisier.
Toate acestea sunt operatii de conversie de structuri de date.
Linearizarea unei matrice este o conversie de la matrice la vector.
back

DISPERSIE

Este o strucutra de date care stocheaza informatii utile diferite prin stabilirea unui mod de dispunere care eficientizeaza alocarea de memorie.
back

ECHILIBRARE ARBORI

In procesul de adaugare noduri, apar diferente foarte mari intre inaltimile subarborelui stang si, respectiv, subarborelui drept.
Echilibrarea este un proces prin care se realizeaza o redistribuire a nodurilor in arbore incat intre inaltimile celor doi subarbori sa existe o diferenta de cel mult o unitate.
back

EFICIENTA

Alegerea si utilizarea eficienta a structurilor de date se efectueaza in raport cu criterii de perfoirmanta precum:
- minimizarea duratei de executie
- maximizarea gradului de ocupare a memoriei alocate
- maximizarea nivelului de reutilizare a componentelor din biblioteci
- cresterea productivitatii programatorilor
- asigurarea unui nivel maxim de mentenabilitate
- maximizarea nivelului de generalitate.
Aceste criterii nu pot fi atinse simultan.
De aceea se alege un criteriu si se scriu mai multe variante ale aplicatiei cu utilizarea diferitelor structuri de date.
Se fac masuratori.
Se alege structura care satisface cel mai bine criteriul stabilit.
back

EXPRESII DE REFERIRE

Sunt constructii cu ajutorul carora se refera elementele din structurile de date.
a[i] este expresia cu care se refera elementul de pe pozitia i din masivul unidimensional a[].
x[i][j] refera elementul de pe linia i si coloana j din masivul bidimensional x[][].
daca s-au efectuat definirile:
int a=10, int *pa=&a, *ppa=&pa;
expresia **ppa refera continutul zonei de memorie care se afla in variabila pointer pa, variabila a carei adresa se afla in variabila ppa.
Expresia:
*p_list refera un element al unei liste, daca p_list este definita ca pointer spre o variabila de tip struct autoreferit.
Expresia:
p_list->pnext refera elementul din lista a carui adresa este stocata in zona de memorie pusa in corespondenta cu identificatorul pnext.
Expresia:
p_list->info++
conduce la incrementarea cu unu a continutului zonei de memorie a carei adresa se calculeaza astfel:
la adresa continuta de variabila p_list cu care se refera un element dintr-o lista se aduna o deplasare si
se obtine adresa campului info.
Continutul zonei de memorie astfel referit este incrementat.
Expresia:
pvect[i]->pnext
- refera un element dintr-un vector de pointeri cu pvect[i] al carui continut este adresa ZZZ
- la adresa ZZZ se refera o zona de memorie a carei adresa YYY se afla in pointerul pnext
- la adresa YYY se afla continutul zonei de memorie care se prelucreaza.
Cu expresia:
plist==NULL
se verifica daca variabila pointer plist are continutul egal cu NULL
Cu expresia:
proot->pstg->pdrept!=NULL
se verifica daca pointerul pdrept din nodul descendent stang, aflat pe nivelul urmator nivelului radadinii,
nod referit prin pointerul pstg, este cu continut egal cu NULL.
back

FISIER

Structura de date statica.
Se considera o colectivitate formata din elementele C1, C2, C3,...,Cm.
Fiecarui element din colectivitate i se inregistreaza date pentru o caracterizare completa, dupa un sablon pentru care a fost proiectat un articol cu descriptorul struct.
Se construieste prin preluare de date de la tastatura si prin scriere articol de articol.
Lungimea fisierului este data de numarul de articole inscrise in el.
Lungimea fisierului este exprimata si ca numar de baiti ocupati de datele privind colectivitatea pentru care este creat fisierul.
In practica se creaza:
- fisierul muncitorilor care contine informatii despre muncitorii unei organizatii
- fisierul de materiale
- fisierul clientilor
- fisierul furnizorilor.
Operatiile in fisiere sunt:
- creare de fisiere
- adaugare de articole in fisier
- stergere de articole din fisier
- inserare de articole
- modificare de campuri in articole
- sortarea fisierului
- reorganizarea fisierului
- cautarea unui anumit articol.
Functie de scopul pentru care se creaza fisierele, se alege intre modul de organizare secvential, indexat-secvential si modul de organizare directa.
Fisierele in memorie sunt fisierele ale caror articole sunt citite si aduse in totalitate in memorie.
Se efectueaza prelucrari pe toate articolele si la terminarea prelucrarilor, toate articolele sunt rescise in fisier.
Software destinat tuturor operatiilor cu fisiere formeaza SISTEMUL DE GESTIUNE A FISIERELOR.
In cazul in care se creaza fisiere care au corelatii intre articole, se va spune ca exista fisiere cu legaturi.
In articolele unui fisier exiswta informatii privind pozitiile articolelor din alte fisiere.
Traversarea unui fisier revine la a citi articolele din fisier.
back

GRAD DE OCUPARE

Este indicatorul care masoara eficienta cu care este utilizata memoria alocata unei structuri de date.
Gradul de ocupare, Go este dat de relatia:
Go=Liu/(Liu+Lzr)
unde:
Liu - lungimea zonei de memorie ocupata de informatia utila din structura de date
Lzr - lungimea zonei de memorie ocupata de variabilele pointer.
Daca se considera matricea definita cu:
int a[20][90];
in care sunt initializate primele15 linii si primele 57 de coloane, atunci:
- lungimea totala a zonei de memorie ocupata de matrice Lzt, este
Lzt=20*90*Lg(int)=20*90*2=3600baiti
- lungimea zonei ocupata de informatia utila este;
Liu=15*57*Lg(int)=15*57*2=1710baiti
iar gradul de ocupare Go este:
Go=1710/3600=0.47
In cazul in care se considera o lista dubla avand 322 componente in care informatia utila pe o componenta este de 17 baiti, iar variabilele pointer ocupa fiecare cate 2 baiti, atunci:
- lungimea unui element din lista dubla este LD=17+2(baiti pentru pointerul care refera elementu precedent)+2(baiti pentru pointerul care refera elementul urmator= 21 baiti
- Liu=322*21=6762
- Lzr=322*4+2(pointerul cu care se refera primul element al listei duble)=1290baiti
Gradul de ocupare Go, pentru lista dubla este:,br> Go=6762/(6762+1290)=0.84
Trebuie urmarit ca acest grad sa fie:
- cat mai apropiat de 1
- cat mai putin dependent de numarul de componente care alcatuiesc structura.
back

INFORMATIE UTILA

Este un set de campuri din componentele structurilor de date.
daca este vorba de masive definite prin:
int a[100];
float x[24];
char aa[200];
zonele de memorie contin exclusiv numai informatie utila.
Informatia utila este aceea care descrie caracteristicile unei colectivitati si face obiectul prelucrarilor.
Componentele structurilor de date, pe langa informatia utla contin si INFORMATII DE REGASIRE sau INFORMATII DE LEGATURA care sunt variabile pointer sau variabile ce contin pozitii ale articolelor in fisiere.
Informatia utila este complexa desi in toate materialele de prezentare a structurilor de date se da ca informatie utila un camp de tip intreg.
In lista simpla privind studentii dintr-o sectie de facultate, informatia utila este:
- inclusa in structura in care se afla campul cu care se refera capul listei simple.
Aceasta structura defineste un camp cu numele facultatii pentru a nu inscrie la fiecare student aceasta informatie.
struct GEN_LISTA{
char nume_facult[50];
struct lista *plist;
} stud;
O componenta a listei este definita prin:
struct lista{
struct info student;
struc lista *pnext;
};
Informatia utila ceva mai complexa este definita prin:
struct student{
char nume_stud[30];
char prenum_stud[40];
int varsta;
int an_studii;
int note_stud[50];
int licenta_grila;
int licenta_proiect;
};
Si in cazul altor structuri de date prin care se descriu facturi, avize de expeditie, se includ campuri cat mai diferite in structura informatiei utile.
Este important ca programatorul sa gaseasca solutie ca sa nu modifice functiile de parcurgere a structurilor ori de cate ori are o alta structura de informatie utila.
Prelucrarea informatiei utile trebuie externalizata in raport cu componentele bibliotecilor dedicate structurilor de date.
dacda pointerul spre capul listei este p_cap_lista, atunci referirea membrilor structurii student se realizeaza cu expresiile de referire:
p_cap_lista->nume_stud
p_cap_lista->prenum_stud
p_cap_lista->varsta
p_cap_lista->note_stud[i]
p_cap_lista->licenta_grila
p_cap_lista->licenta_proiect
Expresia:
p_cap_lista->pnext->licenta_grila
refera nota de la grila pentru studentul a carui situatie scolara este memorata in elementul urmator celui referit prin variabila pointer p_cap_lista.
back

INTERSCHIMB DE ELEMENTE

daca se considera doua elemente dintr-o lista ELEM_i si ELEM_j, a efectua interschimb, inseamna:
- a interschimba infirmatia utila dintre cele doua elemente prin:
temp=ELEM_i->info;
ELEM_i->info=ELEM_J->info;
ELEM_J->info=temp;
- a interschimba legaturi astfel incat mai intai sa fie referit elementul ELEM_j si dupa aceea sa fie referit ELEM_i desi inainte de interschimbare referirea se efectua invers, primul era referit ELEM_i si mai apoi ELEM_j.
Se interschimba fie elemente adiacente, fie elemente de pe pozitii oarecare.
Procedura de interschimb a elementelor a[k] si a[h] dintr-un vector a[] este:
void intersc_vector(int a[], int k, int h)
{
int temp;
temp=a[k];
a[k]=a[h];
a[h]=temp;
}
Procedura pentru interschimbul a doua elemente adiacente dintr-o lista dubla este:
struct d_LIST * interschimb(struct d_LIST *pdlist, int cheia)
{
struct d_LIST *ptemp=pdlist, *palfa, *pbeta, *pwork;
while (ptemp->pnext) {if(ptemp->info==cheia) {
palfa=ptemp; // adresa elementului baza pentru interschimb
pbeta=ptemp->pnext;// adresa elementului aduiacent
pwork=palfa->pprec;
palfa->pprec=pbeta->pprec; pbeta->pprec=pwork;
pwork=palfa->pnext;
palfa->pnext=pbeta->pnext; pbeta->pnext=pwork;
return (ptemp);
}
ptemp=ptemp->pnext;
}
return (NULL);
}
S-a dorit ca aceasta procedura sa aiba explicit:
- cautarea elementului cu cheia ceruta
- interschimbul propriu-zis
- returnare NULL daca interschimbul nu s-a efectuat sau returnare adresa elementului minterschimbat, daca interschimbul s-a efectuat.
back

LISTA

Este o structura dinamica formata din componente ce contin pointeri cu care se refera componentele in ordinea in care s-a facut alocarea de memorie si initializarea .
Elementele listei difera unele de altele in functie de pozitia pe care o au.
Exista un element , numit primul element al listei sau CAPUL LISTEI.
Adresa acestui element este memorata in variabila pointer utilizata la prelucrarea listei.
Programatorii trebuie sa conserve continutul acestei variabile pointer, numita POINTER SPRE CAPUL LISTEI pentru a nu compromite accesul la componentele listei.
Exista si un ultim element al listei.
Celelalte elemente sunt numite intermediare.
Crearea listei se efectueaza adaugand elemente la ultimul element din lista sau legand noul element la primul astfel incat elementul adaugat devine prim element, cap de lista, iar vechiul cap de lista devine al doilea element.
Intrucat ultimul element din lista nu mai refera alt element, variabila pointer de referire element urmator este initializata cu NULL.
Lista gestioneaza elementele dupa principiul FIFO - first in first out.
back

LISTA CIRCULARA

Lista circulara este aceea in care variabila pointer a ultimului element din lista in loc sa contina NULL, contine adresa primului element al listei.
back

LISTA DUBLA

Este lista ale carei componente contin:
- o informatie utila
- o variabila pointer cu care este referit elementul precedent al listei duble
- o variabila pointer cu care se refera elementul urmator din lista dubla.
back

MATRICE

Este o structura statica formata din elemente de acelasi tip, referite cu doua expresii indiciale, corespunzatoare liniilor si coloanelor.
Ca structura agregata, matricea este un vector de vectori.
back

MATRICE COMPLETA

Este o structura definita ca numar de linii si numar de coloane in care cea mai mare majoritate a elementelor este formata din valori nenule.
Matricea completa se defineste prin:
- tip
- nume
- numar de linii
- numar de coloane.
Refrirea elementelor se efectueaza prin doua structuri repetitive imbricate.
Pentru calculul sumei elementelor matricei definite si initializate la definire prin:
int a[4][3]={1,2,3,4,5,6,7,8,9,10,21,33,147};
se foloseste secventa:
.................
int suma=0,m=4,n=3,i;
for(i=0;i .................
back

MATRICE RARA

Este matricea in care mai putin de 30% diin elemente sunt nenule, celelalte fiind nule.
Se reprezinta prin:
- structuri statice cu ajutorul a 3 vectori ce contin: pozitia liniei, pozitia coloanei si valoarea elementului nenul
- structuri dinamice: liste de liste; lista de baza contin indicii liniilor cu elementelor nenule, iar listele derivate contin indicii coloanelor si valorile elementelor nenule.
Matricea rara definita prin:
0 0 0 0 0 0 4 2 0 0 5
0 0 1 0 0 0 0 0 0 7 0
0 0 0 0 0 0 0 0 0 0 0
1 2 3 4 0 0 0 0 0 0 9
0 0 0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0

va avea in lista de baza 5 elemente pentru ca numai 5 linii din 7 au elemente nenule.
Prima lista derivata are doua elemente.
A doua lista are doua elemente.
A patra lista are 4 elemente.
A cincea lista derivata are doar un element ce corespunde valorii nenule 2 de pe coloana a 8-a.
A 7-a linie are si ea tot un element ce corespunde elementului nenul de pe prima coloana avand valoarea 2.
back

MATRICE BANDA

Matricea banda este acea matrice care are elemente nenule in jurul diagonalei.
Matricea:
1 2 3 0 0 0 0 0 0 0 0
0 3 5 1 0 0 0 0 0 0 0
0 0 7 7 7 0 0 0 0 0 0
0 0 0 1 4 8 0 0 0 0 0
0 0 0 0 9 7 1 0 0 0 0
0 0 0 0 0 6 6 6 0 0 0
0 0 0 0 0 0 5 9 2 0 0
0 0 0 0 0 0 0 6 6 8 0
0 0 0 0 0 0 0 0 3 3 5
0 0 0 0 0 0 0 0 0 2 3
0 0 0 0 0 0 0 0 0 0 8
este o matrice banda.
Se trateaza ca matrice rara.
back

MATRICE TRIUNGHIULARA

este matricea cu elemente nule sub diagonala principala.
Se pun in corespondenta elementele nenule ale matricei cu elementele unui vector.
Matricea a[10][10] triunghiulara:
1 2 3 4 5 6 7 8 9 9 0 3 2 7 6 9 1 2 5 7 0 0 6 9 1 6 4 3 9 1 0 0 0 5 4 3 8 9 1 1 0 0 0 0 3 6 8 1 3 4 0 0 0 0 0 4 1 8 6 9 0 0 0 0 0 0 2 5 4 7 0 0 0 0 0 0 0 2 8 1 0 0 0 0 0 0 0 0 5 3 0 0 0 0 0 0 0 0 0 6 se memoreaza in vectorul b[55] astfel:
b[0]=1 b[1]=2 b[2]=3 b[3]=4 b[4]=5 b[5]=6 b[6]=7 b[7]=8 b[8]=9 b[9]=9
b[10]=3 b[11]=2 b[12]=7 b[13]=6 b[14]=9 b[15]=1 b[16]=2 b[17]=5 b[18]=7
b[19]=6 b[20]=9 b[21]=1 b[22]=6 b[23]=4 b[24]=3 b[25]=9 b[26]=1
b[27]=5 b[28]=4 b[29]=3 b[30]=8 b[31]=9 b[32]=1 b[33]=1
b[34]=3 b[35]=6 b[36]=8 b[37]=1 b[38]=3 b[39]=4
b[40]=4 b[41]=1 b[42]=8 b[43]=6 b[44]=9
b[45]=2 b[46]=5 b[47]=4 b[48]=7
b[49]=2 b[50]=8 b[51]=1
b[52]=5 b[53]=3 b[54]=6
back

MATRICE SIMETRICA

Este matricea cu N linii si N coloane pentru care a[i][j]=a[j][i]
Matricea:
1 2 3 4 5 6
2 0 6 9 2 7
3 6 1 5 7 2
4 9 5 1 8 9
5 2 7 8 3 1
6 7 2 9 1 4
este o matrice simetrica.
Memorarea se efectueaza pentru elementele de deasupra diagonalei in bectorul b[] dupa relatia
b[i*N+j]=a[i][j] pentru i=0,1,2,3,..,N-1 procedura pentru verificarea daca o matrice este simetrica este:
int simetrica(int a[][N], int n)
{
int i,j, vb=1;
for(i=0;i for(j=0;j if(a[i][j]!=a[j][i]) return(0);
return(1);
}
back

MODELUL ANALITIC

Presupune descrierea foarte riguroasa a structurii de date folosind o serie de functii precum:
addr() - indica adresa elementului
cont() - continutul elementului
lg() - lungimea in baiti ocupata de element
tip() - tipul elementului
succ() - succesorul elementului
pred() - predecesorul elementului. Un vector definit prin:
float alfa[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,57,18,19,20};
se descrie riguros astfel:
tip(alfa[0])=tip(alfa[1])=....=tip(alfa[19])=float
lg(alfa[0])=lg(alfa[1])=....=lg(alfa[19])=lg(float)=4
succ(alfa[i])=alfa[i+1], i=0,1,2,3,...,18
succ(alfa[19])=NULL
pred(alfa[i])=alfa[i-1], i=1,2,...,19
pred(alfa[0])=NULL
pred(succ(alfa[i]))=alfa[i]
succ(pred(alfa[i]))=alfa[i]
cont(alfa[12])=12
cont(alfa[17])=57
addr(alfa[1])=addr(alfa[0])+lg(float)
addr(alfa[i])=addr(alfa[0])+i*lg(float)
back

MODELUL BAZAT PE GRAFUL ASOCIAT

Consta in a desena pentru fiecare element din structura un nod si a lega nodurile cu arce, exact cum se construieste un graf la disciplina de cercetari operationale.
back

MODELUL GRAFIC

Presupune reprezentarea elementelor care alcatuiesc structura sub forma unor dreptunghiuri in care se diferentiaza pointerii care asigura legaturile si informatia utila.
Pentru lista simpla desenul asociat unei componente are in alcatuire doua dreptunghiuri alipite, unul pentru informatia utila si altul pentru pointerul de referire a elementului urmator din lista.
Vectorul se reprezinta ca un sir de dreptunghiuri lipite unul de altul.
Numarul de dreptunghiuri este egal cu numarul de element din vector.
Matricea se reprezinta prin:
- un vector de pointeri caruia ii corespunde un sir de dreptunghiuri lipite unulk de altul, egal ca numar cu numarul de linii din matrice
- de fiecare element din vectorul de pointeri se dezvolta o legatura spre un sir de dreptunghiuri lipite unul de latul, avand numarul de elemente egal cu numarul de coloane a amtricei.
Mai apare si un dreptunghi cu care se refera vectorul de pointeri, el reprezentatnd un pointer spre pointeri.
back

MODELUL CONSTRUIT CU LIMBAJUL C++

Masivul unidimensional se defineste prin:
tip nume[numar-componente];
referirea elementelor se efectueaza prin:
nume[expresie-indiciala]
Un articol se defineste prin:
struct nume{
tip1 nume1:
tip2 nume2:
......
tip-n nume-n:
};
Nodul radacina al unui arbore oarecare cu cel mult 17 descendenti este definit prin:
struct ARBORE_OARECARE {
int informatia_utila;
struct ARBORE_OARECARE *p_descendent[17];
}proot;
back

MODELUL TEXTUAL

Este bazat pe utilizarea unei descrieiri cat mai riguroase folosind cuvintele limbii romane, de exemplu.
VECTORUL este o insiruire de elemente care ocupa zone de memorie de aceeasi lungime, lipite unele de altele, al caroro continut este interpretat dupa aceleasi reguli. Vectorul se refera in intregime sau pe elemente.
ARBORELE BINAR PEFECT ECHILIBRAT este o structura dinamica formata din elemente dispuse pe niveluri.
Pe primul nivel se afla un singur nod, numit nod radacina, care nu are nod parinte.
Nodul radacina si nodurile intermediare au obligatoriu cate doi descendenti.
Nodurile de pe ultimul nivel nu au descendenti.
Aceste noduri se numesc NODURI FRUNZA.
Daca arborele perfect echilibrat are 5 biveluir:
- pe primul nivel se afla nodul radacina, unul singur
- pe al doilea nivel se afla cei doi descendenti ai nodului radacina
- pe nivelul al treilea se afla 4 descendenti
- pe nivelul al patrulea se afla 8 descendenti
- pe ultimul nivel se afla 16 descendenti.
In total arborele este compus din 1_2_4_8_16 noduri adica 31 noduri sau 2 la puterea a 5-a sin care se scade o unitate.
Un arbore echilibrat perfect cu N niveluri va avea 2 la puterea N -1 noduri, daca numararea nivelurilor incepe cu ZERO.
back

MODIFICARE

Proces prin care se schimba continutul unei zone de memorie, informatie utila sau legaturi.
Modificarile la nivelul structurilor de date vizeaza in sens mai larg:
- schimbarea numarului de elemente prin stergere sau prin adaugare
- schimbarea legaturilor dintre elemente, modificand ordinea si sensul referirilor.
back

NORMALIZARE

Operatie care restabileste proprietatile structurilor de date.
daca se defineste o lista ca avand toate elementele cu informatie utila diferita de zero si daca dupa efectuarea unor prelucrari se obtin elemente in lista cu informatie utila nula, a NORMALIZA revine la a STERGE elementele nule.
Dupa normalizare toate elementele listei recapata proprietatea ca sunt nenule.
back

NUMARARE

Se construiesc proceduri care:
- numara elementele unei liste
- numara elementele unui arbore binar
- numara articolele dintr-un fisier
- numara nivelurile pe care sunt dispuse nodurile unui arbore binar
- numara nodurile dintr-un graf
- numara elementele dintr-o matrice.
back

OBIECTUL ARBORE BINAR

.....IN LUCRU........
back

OBIECTUL LISTA SIMPLA

.....IN LUCRU........
back

OBIECTUL LISTA DUBLA

.....IN LUCRU........
back

OBIECTUL MATRICE

.....IN LUCRU........
back

OBIECTUL STIVA

.....IN LUCRU........
back

OBIECTUL VECTOR

.....IN LUCRU........
back

OBIECTUL B-arbore

.....IN LUCRU........
back

PARAMETRI STRUCTURILOR DE DATE

Lungimea unei structuri de date este data de numarul de componente care alcatuiesc structura.
Procedurile care numara componente de fapt dau lungimea structurii.
Inaltimea unui arbore este data de numarul de niveluri pe care sunt dispune nodurile.
Complexitatea CH in sens HALSTEAD a unei structuri de date este data de:
- numarul de componente N
- numarul de arce existent intre componente M
si de relatia:
CH=N*LG2(N)+M*LG2(M)
unde LG2(x) este logaritmul in baza 2 din x.
Pentru o lista simpla cu RR componente se definesc:
RR-1 legaturi intre componente
RR componente
CH=RR*LH2(RR)+(RR-1)*LG2(RR-1)
Legatura dintre pointerul care refera primul element nu este luata in considerare in aceasta definire.
In cazul in care se ia in calcul si aceasta legatura, atunci, pentru lista simpla complexitatea este:
CH=2*RR*LG2(RR).
back

PROCEDURI

Procedurile care lucreaza cu structuri de date se caracterizeaza prin:
- tipul de date returnat care este void daca nu returneaza ceva special, tip int daca returneaza un rezultat intreg obtinut prin calcule, pointer spre tipul ce defineste elemente daca returneaza referirea unei noi structuri, referirea unui element cautat din structura
- lista de parametri ce contine informatii despre structura care face obiectul prelucrarii si informatii despre un anumit element
- instructiune care asigura stocarea informatiilor privind adresa primului element din structura, pentru a relua prelucrari de la acesta
- secventa de instructiuni repetitive
instructiunea care asigura avansul spre elementul urmator din structura
- returnarea rezultatului prelucrarii.
back

PROCEDURI NERECURSIVE

Contin:
- linia de cod de definire procedura: tip rezultat returnat, nume, lista de parametri
- memorarea adresei primului element
- structura while() sau for() pentru traversarea structurii
- instructiune pentru asigurarea trecerii de la un element la altul al structurii
- returnare rezultat.
back

PROCEDURI RECURSIVE

Contin:
- linia de definire cu tip rezultat returnat, nume procedura, lista de parametri
- o conditie cu care se initializeaza o variabila
- autoapelul procedurii ce include si expresia de referire element urmator.
back

SORTARE LISTA

Este rezultatul unui interschimb de informatie utila intre elemente sau interschimb de legaturi astfel incat elementele ce compun lista sa fie dispuse in ordine crescatoare sau in ordine descrescatoare,in raport cu cheile care individualizeaza fiecare element al listei, chei dupa cum s-a facut sortarea.
back

SORTARE MATRICE

Proces de interschimb linii sau coloane sau elemente din matrice astfel incat sa se obtina indeplinirea unei conditii impuse printr-un enunt.
back

SORTARE VECTOR

Interschimbul dintre elementele unui vector x[] pana se obtine indeplinirea conditiei:
x[i] daca s-a cerut ca sortarea sa fie crescatoare
sau
x[i]>x[i+1]
daca s-a cerut ca sortarea sa fie descrescatoare.
back

STERGERE ELEMENT

Revine la a dealoca memoria asociata unui element a carui cheie a fost specificata sau a carui pozitie in structura a fost data.
Este important sa se asigure noile legaturi intre elementul care precede elemntul care face obiectul stergerii si elementul care urmeaza elementului sters.
Procedura de stergere element returneaza informatia daca s-a facut sau nu cu succes operatia de stergere.
Se sterge un element din lista, se sterge o frunza dintr-un arbore.
Sunt cazuri in care stergerea unui element din structura dinamica produce modificari de substanta in structura asa cum se intampla in cazul arborilor B.
back

STERGERE STRUCTURA

Inseamna operatia de dealocare de memorie din aproape in aproape, pana cand structura nu mai contine nici un element.
Variabila pointer cu care s-a referit primul element din structura contine dupa stergerea structurii NULL.
back

STIVA

Structura dinamica in care alocarea si dealocarea se realizeaza dupa principiul LIFO - last in first out.
Operatiile pe stiva supt PUSH in care se aloca memorie unui element, informatia este stocata in acest element si respectivul element este pus in structura dinamica, devenind primul element ce va fi referit de variabila pointer cu care se refera elementele acestei structuri dinamice.
Stiva este tot o lista care adaugareea se face la primul element, iar operatiile implementate sunt PUSH, da adaugare la inceput si POP de dealocare a primului element.
Primul element se numeste varful stivei.
Variabiula pointer cu care se efectueaza referirea lemenetelor din aceasta tipologie de liste refera varful stivei.
back

SUBSTRUCTURI DE DATE

Se vorbeste de sublista, ca fiind componente consecutive dintr-o lista bine delimitate, in sensul ca se stie care este prima componenta a sublistei si care este ultima componenta a sublistei.
Subarborele reprezinta totalitatea nodurilor descendente in raport cu o variabila pointer care refera partea stanga sau partea dreapta, care se afla intr-un nod parinte.
Subvectorul delimitat de componentele x[4] si x[10] ale vectorului definit prin:
int x[100];
include componentele consecutive x[4], x[5],...,x[9] si x[10].
Vectorul este subsectorul lui insusi.
Definirea substructurilor creaza sansa lucrului pe parti din structura realizand in acest fel prelucrari particulare pentru fiecare din substructuri, mai ales daca se identifica substructuri disjuncte.
back

STRUCTURI DE DATE ADECVATE

Sunt acele structuri de date care in raport cu o problema de rezolvat:
- asigura generalitate solutiei
- determina expresii de referire cat mai simple
- reutilizeaza cat mai mult proceduri existente
- condul la un grad de ocupare cat mai bun a zonelor de memorie alocate
- necesita efort de mentenanta redus pentru aplicatie in timp.
Pentru aflarea minimului dintre doua numere, utilizarea variabilelor elementare este justificata.
Pentru calculul mediei aritmetice a N elemente trebuie folosit un vector de stocare a elementelor, initializat dintr-un fisier.
In cazul in care se foloseste o variabila elementara, datele trebuie reintroduse ori de cate ori se reia prelucrarea.
daca se folosesc mai multe variabile elementare apar urmatoarele inconveniente:
- lungimea programului depinde de numarul de termeni pentru care se calculeaza media
- orice modificare in sir atrage dupa sine modificarea programului.
Sunt inconvenieinte care fac neadecvate variabilele elementare pentru aceasta problema.
daca se stie cu exactitate numarul de termeni ai sirului, lista simpla este neadecvata.
daca numarul de termeni este necunoscut, in cazul alocarii a o miet de termeni invectori, iar lucru se face numai cu 10 termeni, vectorul alocat static este ineficient din punct de vedere a gradului de ocupare.
back

STRUCTURI DE DATE DINAMICE

Se obtin in procesul alocarii de zone de memorie, initializarii si crearii de legaturi, din aproape in aproape.
Dimensiunile acestor structuri cresc prin procesul de alocare de noi zone sau descresc prin dealocarea zonelor de memorie de care nu mai este nevoie in program.
back

STRUCTURI DE DATE STATICE

Se obtin din alocarea memoriei inainte de lansarea in executie a programului. Aceste structuri nu-si modifica numarul de componente in timpul executiei.
Matricele, vectorii, variabilele de grup definite prin program sunt structuri de date statice.
back

TIPURI DE DATE

Tipurile fundamentale de date sunt:
- intreg
- virgula mobila
- caracter
- sir de caractere
- pointer
- boolean.
De la limbaj de programare la limbaj de programare exista nuante.
Cand se defineste un tip fundamental trebuie sa se:
- precizeze cuvantul cheie cu care respectivul tip este identificat
- defineasca lungimea zonei de memorie care se asociaza zonelor definite cu acel tip pentru variabile
- stabileasca operatiile care se efectueaza cu variabilele de acel tip.
Tipurile de date derivate au mecanisme de constructie, precizate in fiecare limbaj de programare.
Tipul de date autoreferit presupune utilizarea descrierii in campuri incluse in structura care este in curs de construire.
back

SUPRAINCARCARE OPERATORI

Procedeu prin care operatori precum + - * / ++ -- = sunt pusi in corespondenta cu operatii de prelucrare definite pentru structuri de date statice sau dinamice.
Operatorul + se pune in corespondenta cu procedura de concatenare liste simple sau duble astfel incat expresia:
lista1=lista2+lista3
va insemna de fapt concatenarea listei2 cu lista 3 si rezultatul va fi lista1
daca in clasa matrice se supraincarac operatorii + - * si =, expresia:
alfa=beta+gama-delta*eta
inseamna ca:
- se inmultesc matricele delta si eta
- rezultatul este scazul din matricea gama
- rezultatul scaderii este adunat la matricea beta
- rezultaul adunarii este copiat de o procedura in matricea alfa ca operatie de atribuire cu care a fost pusa in corespondenta acea procedura in procesul de supraincarcare.
back

TIPURI DE DATE ABSTRACTE

Constructii formalizate prin care se stabilesc:
- modalitati de definire date
- proprietati date
- operatii care se realizeaza cu datele.
Pentru datele de tip intreg, a defini tipul abstract revine la:
- a preciza alfabetul <0,1,2,3,4,5,6,7,8,9>
- a specifica mecanismul de construire a sirurilor care se interpreteaza ca date de tip intreg
- a defini algoritmul de implementare a adunarii a doua numere intregi
- a defini algoritmul de implementare a scaderii a doua numere intregi
- a defini algoritmul de implementare a inmultirii a doua numere intregi
- a defini algoritmul de implementare a impartirii a doua numere intregi
- a defini algoritmul de implementare a compararii a doua numere intregi.
Definirea tipului de date abstract trebuie sa fie complet si corect, astfel incat sa nu fie doua tipuri distincte care sa aiba aceleasi definiri, ceea ce ar conduce la ambiguitate.
Definirea structurilor de date urmeaza aceleasi reguli.
Formalizarea este mult mai complexa.
back

TRAVERSARE ARBORE

Proces prin care se asigura referirea tuturor nodurilor din structura arborescenta.
Exista traversarea INORDINE, PREORDINE, POSTORDINE.
back

TRAVERSARE LISTA

Proces prin care se refera toate elementele unei liste.
Procedura care asigura traversarea listei include:
- o structura while() sau for() cu care se asigura repetitivitatea procesului de traversare
- atribuirea pointer_list=pointer_list->pnext cu care se asigura referirea urmatorului element din lista.
back

TRAVERSARE MATRICE

Set de instructiuni for() cu care se refera liniile si coloanele matricei.
Referirea elementelor matricei se efectueaza cu expresii de forma:nume[expresie indiciala1][expresie indiciala2];
back

TRAVERSARE VECTOR

Utilizarea instructiunii for() cu care se modifica variabila de control i astfel incat sa fie referite elementele vectoului x[].
back

VALIDARE

Validarea datelor este extrem de necesara in aplicatii pentru a evita:
- lucru cu valori in afara domeniului pentru care se definesc variabilele (salarii negative, cantitati sau preturi negative, valori nenumerice pentru variabile numerice)
- referirea de componente nedefinite ( s-a definit un vector cu 30 de componente si se initializeaza variabila de control cu valoarea 49 si elementl x[48] nu exista.
In cazul structurilor de date validarile vizeaza:
- realizarea cu succes a operatiei pe structura de date
- alocarea de memorie
- gasirea elementului cautat.
Validarea vizeaza testul pe variabile pointer daca sunt sau nu egale cu NULL.
In urma validarilor trebuie:
- sa nu se umple stiva prin alocari fara dealocari simetrice
- sa nu se continue prelucraqrile ca si cum oiperatia dinainte s-a executat corect, cand de fapt ea nu s-a executat corect in realitate.
back

VOLUM PRELUCRARI

Indicator care indica numarul de instructiuni care se executa intr-un program.
Pentru secventa:
................
suma=0;
for(i=0; i .............
volumul de prelucrari VP este dat de relatia:
VP=1+m*(1+n*(1+2*r))
VP=1+m+m*n+2*m*n*r
Pentru secventa:
...................
minim=x[0];
pozmin=0;
for(i=1;i {
if(minim>x[i]){
minim=x[i];
pozmin=i;
}
..................
volumul VP de prelucrari este dat de relatia:
VP=2+(n-1)*(2+q*2)
unde q reprezinta probabilitatea ca minim>x[i]
back

ZONA DE MEMORIE

este un sir de baiti adiacenti caracterizat prin:
- lungime
- adresa de inceput
- continut
- semnificatie data de context
- nume asociat.
back

........

back